#include "drawing.h"
#include "graph_utils.h"
#include <ppl.h>
#include <tuple>
#include <concurrent_vector.h>

#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/variate_generator.hpp>

typedef std::pair<my_edge_t,bool> tabu_move ;

void add_edges(Graph & g,
			   my_edge_t & edge)
{
	auto vertices = boost::vertices(g);
	std::vector<Graph::vertex_descriptor> v(2);
	std::copy_if(vertices.first,
				 vertices.second,
				 v.begin(),
				 [&g,&edge](Graph::vertex_descriptor b){return g[b] == edge.first || g[b] == edge.second ;}
				 );
	//auto v1 = v[0];
	//auto v2 = v[1];
	//auto edge_p = make_edge(g[v1],g[v2]);
   boost::add_edge(v[0],v[1],make_edge(g[v[0]],g[v[1]]),g);
};

void remove_edges(Graph &g,my_edge_t & edge)
{
	boost::vertices(g); 
	boost::remove_edge_if([&g,&edge](Graph::edge_descriptor e){ return g[e] == edge;},g);
};

void voisinage1(Graph & g,std::vector<tabu_move> & voisins,std::set<my_edge_t> edges){
	for (auto it = edges.begin(); it != edges.end();++it)
	{
		voisins.push_back(std::make_pair(*it,true));
	}
}

void voisinage2(Graph & g,std::vector<tabu_move> & voisins,
				std::set<my_edge_t> & edges,
				std::set<my_edge_t> & all_edges) 
{

	std::set<my_edge_t> absent;
	std::set_difference(all_edges.begin(),all_edges.end(),edges.begin(),edges.end(),std::inserter(absent,absent.begin()));
	std::transform(absent.begin(),absent.end(),std::back_inserter(voisins),[](my_edge_t e){ return std::make_pair(e,false);})  ;
}
/*
void voisinage_intelligent(Graph & g ,
						   Graph &tree,
						   Graph &forest,
)
{
	std::vector<my_edge_t> edges;
	
	auto forest_vertices = boost::vertices(forest);
	auto tree_vertices = boost::vertices(tree);

	for(auto it1 = tree_vertices.first; it1 != tree_vertices.second;++it1)
		for(it2 = forest_vertices.first; it2!+ forest_vertices.second;++it2)
	auto best_move = m->first;
	auto best_tree = trees[best_move];
	auto best_forest = forests[best_move];
}
*/
void voisinage(Graph & g ,
			   std::vector<tabu_move> & voisins,
			   std::set<my_edge_t> edges,
			   std::set<my_edge_t> all_edges)
{
	voisinage1(g,voisins,edges);
	voisinage2(g,voisins,edges,all_edges);
}

Graph solution_initiale(int nombre_vertex,boost::minstd_rand & rn) {
	Graph g ;
	for (int i = 1 ; i < nombre_vertex +1; ++i)
	{
		auto v = boost::add_vertex(i,g);
	}
	auto vertices = boost::vertices(g) ;
	for(auto it = vertices.first; it != vertices.second;++it){
		auto it2 = it;
		++it2;
		for(; it2 != vertices.second;++it2)
			boost::add_edge(*it,*it2,g);
	}
	
	int count_edge = 0;
	for (auto it = boost::edges(g).first; it != boost::edges(g).second;++it,count_edge++)
		g[*it] = make_edge(g[it->m_source],g[it->m_target]);
	
	
	auto temp = std::map<Graph::vertex_descriptor,boost::default_color_type>() ;
	std::map<Graph::vertex_descriptor,Graph::vertex_descriptor> temp2 = std::map<Graph::vertex_descriptor,Graph::vertex_descriptor>() ;
	boost::associative_property_map< std::map<Graph::vertex_descriptor,boost::default_color_type> >  color(temp);
	boost::associative_property_map< std::map<Graph::vertex_descriptor,Graph::vertex_descriptor> >    preds(temp2);
	
	boost::random_spanning_tree(g,rn,boost::color_map(color).predecessor_map(preds) );	
	std::vector<Graph::vertex_descriptor> v1;
	auto predicate = [&g,&preds](Graph::edge_descriptor v)  { return ! ((preds[v.m_source] == v.m_target) || (preds[v.m_target] == v.m_source)) ;} ;
	remove_edge_if(predicate,g);
	return g ;

};

int h_maximal_tree(Graph & g,boost::variate_generator<boost::mt19937&, boost::uniform_int<> > & die,int mode = 2,std::string result_name = "h_maximal_tree"){	
	typedef std::function<int (Graph::vertex_descriptor v,
		std::set<Graph::vertex_descriptor> & selected_vertices,
		std::set<Graph::vertex_descriptor> & candidates)> eval_t ;

	auto eval_vertex1 = [&g](Graph::vertex_descriptor v,
		std::set<Graph::vertex_descriptor> & selected_vertices,
		std::set<Graph::vertex_descriptor> & candidates) -> int
	{
		auto adjacents = boost::adjacent_vertices(v,g);
		auto adjacent_set = std::set<Graph::vertex_descriptor>(adjacents.first,adjacents.second);

		auto set_diff = std::set<Graph::vertex_descriptor>() ;

		std::set_intersection(selected_vertices.begin(),
			selected_vertices.end(),
			adjacent_set.begin(),
			adjacent_set.end(),
			std::inserter(set_diff,set_diff.begin()));
		
		if (set_diff.size() > 1) //induit un cycle 
			return -1;
		
		return boost::degree(v,g) ;

	};

	auto eval_vertex2 = [&g](Graph::vertex_descriptor v,
							 std::set<Graph::vertex_descriptor> & selected_vertices,
							 std::set<Graph::vertex_descriptor> & candidates) -> int
	{
		auto adjacents = boost::adjacent_vertices(v,g);
		auto adjacent_set = std::set<Graph::vertex_descriptor>(adjacents.first,adjacents.second);
		
		auto set_diff = std::set<Graph::vertex_descriptor>() ;
		
		std::set_intersection(selected_vertices.begin(),
							  selected_vertices.end(),
							  adjacent_set.begin(),
							  adjacent_set.end(),
							  std::inserter(set_diff,set_diff.begin()));
		if (set_diff.size() > 1) //induit un cycle 
			return -1;

		set_diff.clear();
		
		std::set_difference(adjacent_set.begin(),
							  adjacent_set.end(),
							  candidates.begin(),
							  candidates.end(),
							  std::inserter(set_diff,set_diff.begin()));
		
		return (set_diff.size());
	} ;

	eval_t eval_vertex  = (mode == 1 ) ? eval_t(eval_vertex1) : eval_t(eval_vertex2) ; 
	auto vertices = boost::vertices(g);
	auto selected_vertices = std::set<Graph::vertex_descriptor>();
	auto selected_edges = std::set<Graph::edge_descriptor>();
	auto entourage = std::set<Graph::vertex_descriptor>() ;
	
	auto i = die() % (boost::num_vertices(g));
	/*auto max_degree_vertex = *std::max_element(vertices.first,
									   vertices.second,
									   [&g](Graph::vertex_descriptor u,Graph::vertex_descriptor v)
												{ return boost::degree(u,g) <  boost::degree(v,g);});
	*/
	auto temp = vertices.first ;
	std::advance(temp,i);
	auto max_degree_vertex = *temp ;
	auto adjs = boost::adjacent_vertices(max_degree_vertex,g);
	
	selected_vertices.insert(max_degree_vertex);
	entourage.insert(adjs.first,adjs.second);

	while(true)
	{
		
		if (entourage.size() == 0)
		{
			
			//std::cout << "Plus de candidats valide" << std::endl ;
			//auto m = std::set<my_edge_t>();
			//std::transform(selected_edges.begin(),
			//	selected_edges.end(),
			//	std::inserter(m,m.begin()),
			//	[&g](Graph::edge_descriptor e){return g[e];});
			auto n = std::set<my_vertex_t>();
			auto all_node = std::set<my_vertex_t>();
			auto set_diff = std::set<my_vertex_t>();
			std::transform(selected_vertices.begin(),
				selected_vertices.end(),
				std::inserter(n,n.begin()),
				[&g](Graph::vertex_descriptor v){return g[v];});
			//display_graph(g,result_name+"_"+boost::lexical_cast<std::string>(mode),m,n);
			auto vertices = boost::vertices(g);
			std::transform(vertices.first,
				vertices.second,
				std::inserter(all_node,all_node.begin()),
				[&g](Graph::vertex_descriptor v){return g[v];});
			std::set_difference(all_node.begin(),
								all_node.end(),
								n.begin(),
								n.end(),std::inserter(set_diff,set_diff.begin()));
			remove_vertices(set_diff,g);
			return selected_vertices.size() ; 
		}
		

		auto set_union = std::set<Graph::vertex_descriptor>() ;
		
		std::set_union(selected_vertices.begin(),
					   selected_vertices.end(),
					   entourage.begin(),
					   entourage.end(),
					   std::inserter(set_union,set_union.begin()));
		
		auto qualities = std::map<Graph::vertex_descriptor,int>();
		
		std::transform(entourage.begin(),
					   entourage.end(),
					   std::inserter(qualities,qualities.begin()),
					   [&selected_vertices,&set_union,&eval_vertex]
									(Graph::vertex_descriptor v)
										{return std::make_pair(v,eval_vertex(v,selected_vertices,set_union)) ;}
					) ;

		auto best_vertex = *std::max_element(entourage.begin(),
											 entourage.end(),
											 [&qualities] 
											 (Graph::vertex_descriptor u, Graph::vertex_descriptor v) mutable -> bool  
												{ return qualities[u] < qualities[v] ;});
	
		if (qualities[best_vertex] == -1)
		{
			//std::cout << "Plus de candidats valide" << std::endl ;
			//auto m = std::set<my_edge_t>();
			//std::transform(selected_edges.begin(),
			//	selected_edges.end(),
			//	std::inserter(m,m.begin()),
			//	[&g](Graph::edge_descriptor e){return g[e];});
			auto n = std::set<my_vertex_t>();
			auto all_node = std::set<my_vertex_t>();
			auto set_diff = std::set<my_vertex_t>();
			std::transform(selected_vertices.begin(),
				selected_vertices.end(),
				std::inserter(n,n.begin()),
				[&g](Graph::vertex_descriptor v){return g[v];});
			//display_graph(g,result_name+"_"+boost::lexical_cast<std::string>(mode),m,n);
			auto vertices = boost::vertices(g);
			std::transform(vertices.first,
				vertices.second,
				std::inserter(all_node,all_node.begin()),
				[&g](Graph::vertex_descriptor v){return g[v];});
			std::set_difference(all_node.begin(),
				all_node.end(),
				n.begin(),
				n.end(),std::inserter(set_diff,set_diff.begin()));
			remove_vertices(set_diff,g);
			return selected_vertices.size() ; 
		}

		selected_vertices.insert(best_vertex);
		entourage.erase(best_vertex);
		auto outs = boost::out_edges(best_vertex,g);
		auto edge_to_add = *std::find_if(outs.first,outs.second,[&g,&selected_vertices](Graph::edge_descriptor e){ return selected_vertices.find(boost::target(e,g)) != selected_vertices.end() ;});
		selected_edges.insert(edge_to_add);
		//std::set<Graph::vertex_descriptor> p = std::set<Graph::vertex_descriptor>() ; 
		std::copy_if(boost::adjacent_vertices(best_vertex,g).first,
					 boost::adjacent_vertices(best_vertex,g).second,
					 std::inserter(entourage,entourage.begin()),
					 [&selected_vertices](Graph::vertex_descriptor v)
						{ return selected_vertices.find(v) == selected_vertices.end() ;});

	};
	throw "something strange" ;
 	auto n = std::set<my_vertex_t>();
	auto m = std::set<my_edge_t>();
	
	std::transform(selected_edges.begin(),
				   selected_edges.end(),
				   std::inserter(m,m.begin()),
				   [&g](Graph::edge_descriptor e){return g[e];});
	
	std::transform(selected_vertices.begin(),
		selected_vertices.end(),
		std::inserter(n,n.begin()),
		[&g](Graph::vertex_descriptor v){return g[v];});
	display_graph(g,result_name+"_"+boost::lexical_cast<std::string>(mode),m,n);
	remove_vertices(n,g);
	return selected_vertices.size() ;
};

int h_maximal_forest_(Graph & g,std::set<my_vertex_t> & vertex_to_remove,const std::map<int,Graph::vertex_descriptor> & descs) 
{
	remove_vertices(vertex_to_remove,g,descs);
	return intensify(g);
}

int h_maximal_forest(Graph & g )
{

	//selection les points les plus prometeurs :
	//Plusieurs strategie de selection pour les node prometeur...
	//1-les rangers par ordre croissants de dedree et choisir un nombre fixe
	//2- meme chose choisir un pourcentage...
	//3 choisir un enssemble de noeud qui fait un certain pourcentage du nombre totale des arretes...
	//4-regarder dans les modules....

	auto good_nodes = std::vector<Graph::vertex_descriptor>();	
	auto good_node1 = [&good_nodes](Graph & g) {
		std::vector<Graph::vertex_descriptor> v(boost::vertices(g).first,boost::vertices(g).second);
		std::sort(v.begin(),v.end(),[&g](Graph::vertex_descriptor x , Graph::vertex_descriptor y ){ return (boost::degree(x,g) > boost::degree(y,g));});
		//choisir les 10 vertices les meilleurs
		auto end = (boost::num_vertices(g) > 10) ? (v.begin() + 8) : (v.end()) ;
		std::copy(v.begin(),end,std::back_inserter(good_nodes));
		; };
	good_node1(g);
	
	//std::cout << "Node selected : " <<std::endl ;
	
	//for(auto it = good_nodes.begin();it != good_nodes.end();++it)
	//	std::cout << g[*it] << " : " << boost::degree(*it,g) <<std::endl ;
	auto vertices = boost::vertices(g);
	auto graph_size = std::distance(vertices.first,vertices.second);

	std::set<my_vertex_t> m ;
	std::transform(good_nodes.begin(),good_nodes.end(),std::inserter(m,m.begin()),[&g](Graph::vertex_descriptor v) {return g[v] ;});
	
	int count = 0 ;
	Concurrency::concurrent_vector<std::pair<Graph,int> > res ;
	std::pair<Graph ,int> absolute_best ;
	//int absolute_best = 0 ;
	while(true){
		++count;
		std::vector<std::set<my_vertex_t>> subsets = generate_subset(count,m.begin(),m.end());	
		res.clear();
		Concurrency::parallel_for_each(subsets.begin(),subsets.end(),[&res,&g](std::set<my_vertex_t> & vertex_to_remove) {
					std::map<int,Graph::vertex_descriptor> useless;
					Graph cp = g;
					int maximal_f = h_maximal_forest_(cp,vertex_to_remove,useless);
					res.push_back(std::make_pair(cp,boost::num_vertices(cp)));
				;});
	    
		auto best = *std::max_element(res.begin(),res.end(),[](std::pair<Graph,int>  & el1,
															   std::pair<Graph,int>  & el2) mutable -> bool { return el1.second < el2.second;});
		
		if ( best.second > absolute_best.second  )
			absolute_best = best ;

		//si on on a deja trouver un arbre plus grand que le nombre de retirer a la base sert  rien
		if (absolute_best.second > (graph_size - count))
			break;

		if (count == m.size())
			break ;

	}
	g = absolute_best.first ;
	return absolute_best.second ;
}

void generate_all_possible_edge(Graph & g , std::set<my_edge_t> & all_edges)
{
	auto vertices = boost::vertices(g);
	for (auto it = vertices.first; it != vertices.second;++it ){
		auto it2 = it ;
		it2++;
		for (; it2 != vertices.second;++it2)
			all_edges.insert(make_edge(g[*it],g[*it2]));
	};
}

void apply_move(Graph &g,
				tabu_move move)
{
	if (move.second == false)
		 add_edges(g,move.first);
	else
		remove_edges(g,move.first);
};
std::string print_move(tabu_move move)
{
	return (move.second ? "Retirer " : "Ajouter ") + boost::lexical_cast<std::string>(move.first.first) + " -- " + boost::lexical_cast<std::string>(move.first.second); 
}
int heuristique1 (Graph & solution,
				  Graph & foret,
				  Graph & arbre,
				  int nb_vertices,
				  int iter_max = 200,
				  int tabu_max = 23) 
{
	std::cout << "iter " << iter_max << std::endl ;
	auto rn = boost::minstd_rand(std::time(0)) ;
	std::vector<tabu_move> voisins;
	std::map<tabu_move,int> voisins_quality;
	boost::circular_buffer<tabu_move> tabu_list(tabu_max) ; 
	auto g0 = solution_initiale(nb_vertices,rn);
	std::set<my_edge_t> all_edges; 
	std::set<my_edge_t> edges ;
	generate_all_possible_edge(g0,all_edges);
	auto seed = std::time(0);
	boost::mt19937 gen(seed) ;
	boost::uniform_int<> dist(0, all_edges.size() - 1);
	boost::variate_generator<boost::mt19937&, boost::uniform_int<> > die(gen, dist);
	Graph all_time_best,all_time_best_tree,all_time_best_forest ;
	int all_time_best_quality = 0 ;


	//display_graph(g0,"solution_initiale_h.dot");
	
	auto vertices = boost::vertices(g0);
	std::map<Graph::vertex_descriptor,int> component_map_ ;
	std::map<Graph::vertex_descriptor,boost::default_color_type> v_col;
	for (auto it = vertices.first;it != vertices.second;++it)
	{
		component_map_.insert(std::make_pair(*it,0));
		v_col.insert(std::make_pair(*it,boost::white_color));
	}
	boost::associative_property_map< std::map<Graph::vertex_descriptor,boost::default_color_type> >    vertex_color(v_col);
	boost::associative_property_map< std::map<Graph::vertex_descriptor,int> >    component_map(component_map_);

	for (int a = 0; a < iter_max;++a)
	{
		edges.clear();
		auto edges_ = boost::edges(g0);
		std::transform(edges_.first,edges_.second,std::inserter(edges,edges.begin()),[&g0](Graph::edge_descriptor e){return g0[e] ;});
		voisins.clear();
		voisins_quality.clear();
		
		voisinage(g0,voisins,edges,all_edges);
		
		std::cout << "Voisins " << std::endl ;
		//for (auto it = voisins.begin();it != voisins.end();++it)
		//	std::cout << print_move(*it) << std::endl;

		std::set<tabu_move> s1(voisins.begin(),voisins.end());
		std::set<tabu_move> s2(tabu_list.begin(),tabu_list.end());
		std::vector<tabu_move> v4 ;
		std::set<tabu_move> v5 ;
		std::set_difference(s1.begin(),s1.end(),s2.begin(),s2.end(),std::back_inserter(v4));
		if (v4.size() == 0) //aucun mouvement possible
		{
			tabu_list.clear();
			continue ;
		}
		
		for(int i  = 0; i < 200; ++i){
			auto r = die() % v4.size();
			v5.insert(v4[r]);
		}

		std::vector<tabu_move> v3(v5.begin(),v5.end());
		//std::cout << "Voisins apres tabu " << std::endl ;
		//for (auto it = v3.begin();it != v3.end();++it)
		//	std::cout << print_move(*it) << std::endl;
		
		///////////////////Version sequentielle
		std::map<tabu_move,Graph> trees;
		std::map<tabu_move,Graph> forests;
		for (int i = 0 ; i < v3.size();++i )
		{
			//std::cout << i << " : " <<  v3.size() << std::endl ;
			auto res = trees.insert(std::make_pair(v3[i],g0));
			res.second ;
			apply_move(trees[v3[i]],v3[i]);
			int nb_component = boost::connected_components(trees[v3[i]],component_map,boost::vertex_color_map(vertex_color));
			if (nb_component > 1)
				continue ;
			forests.insert(std::make_pair(v3[i],g0));
			apply_move(forests[v3[i]],v3[i]);
			int f = h_maximal_forest(forests[v3[i]]) ;
			Graph co_max ;
			int t_max  = 0;
			for (auto l = 0 ; l < 20 ; ++l){
				auto co = trees[v3[i]] ;
				int t = h_maximal_tree(co,die) ;
				if (t > t_max)
				{
					co_max = co ;
					t_max = t ;
				}
			}
			trees[v3[i]] = co_max;
			voisins_quality.insert(std::make_pair(v3[i],f -  t_max)) ;
		}
		/////////////////Fin vertion sequentielle

		auto m = std::max_element(voisins_quality.begin(),voisins_quality.end(),[](std::pair<tabu_move,int> e1,std::pair<tabu_move,int> e2){ return e1.second < e2.second ;});
		auto best_move = m->first;
		apply_move(g0,best_move);
		
		if (m->second > all_time_best_quality)
		{
			all_time_best_tree = trees[best_move];
			all_time_best_forest = forests[best_move];
			all_time_best = g0 ;
		}
		//std::cout << "best move : " << print_move(best_move) <<" Obecjetive : " << m->second << std::endl;
		//display_graph(g0,"solution_etape_"+boost::lexical_cast<std::string>(a)+".dot");
		//display_subgraph(g0,best_tree,"arbremaximal_etape_"+boost::lexical_cast<std::string>(a)+".dot");
		//display_subgraph(g0,best_forest,"forestmaximal_etape_"+boost::lexical_cast<std::string>(a)+".dot");
		tabu_list.push_back(std::make_pair(best_move.first,!best_move.second));
	};
	arbre = all_time_best_tree;//auto best_tree = trees[best_move];
	foret = all_time_best_forest;
	solution = all_time_best ;
	return boost::num_vertices(solution) ;
}

int test_maximal_forest(boost::minstd_rand & rn)
{
	
	desc2int_t d;
	int2desc_t b;
	for(int i = 0 ; i < 200 ;++i){
		Graph  g;
		boost::generate_random_graph<>(g,30,40,rn,false,false);
		int count = 0 ;
		for(auto it = boost::vertices(g).first ; it != boost::vertices(g).second;++it,++count)
			g[*it] = count; //count;

		count = 0 ;
		for(auto it = boost::edges(g).first ; it != boost::edges(g).second;++it,++count)
			g[*it] = make_edge(g[it->m_source],g[it->m_target]); //count;
		Graph cp1 = g ;
		Graph cp2 = g ;
		std::cout << boost::num_vertices(g) <<std::endl;
//		std::cout << "exact_graph " << exact_maximal_forest(cp1,d,b) << std::endl ;
//		display_subgraph(g,cp1,"exact_forest");
		//std::cout << "heuristique_graph " << h_maximal_forest(cp2) << std::endl ;
		//display_subgraph(g,cp2,"heuriste_forest");
		print_graph_cycle(g);
	};
	return  0;
}

